package queue;

/**
 * 顺序循环队列类，实现队列接口
 *
 * @param <T>
 * @author wt
 */
public class SeqQueue<T> implements QQueue<T> {
    private T element[]; // 存储队列数据元素的数组
    private int front, rear; // front、rear分别为队列头尾下标(指针指示器)
    int tag = 0; // 1:满 , 0:空

    /**
     * 构造容量为length的空队列
     *
     * @param length
     */
    public SeqQueue(int length) {
        if (length < 64)
            length = 64; // 设置队列数组容量最小值
        this.element = (T[]) new Object[Math.abs(length)];
        this.front = this.rear = 0; // 设置空队列
    }

    /**
     * 构造默认容量的空队列
     */
    public SeqQueue() {
        this(64);
    }

    public SeqQueue(T[] arr) {
        this.front = this.rear = 0;
        this.element = (T[]) new Object[Math.abs(arr.length)];
        for (int i = 0; i < element.length; i++) {
            this.enQueueByTag(arr[i]);
        }
    }

    /*
     * 判断队列是否空，若空返回true
     *
     * @see queue.QQueue#isEmpty()
     */
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public T getHead() {
//        if (!isEmpty()) {
        if (tag != 0) {
            return element[front];
        }
        return null;
    }

    /*
     * 元素x入队，空对象不能入队
     */
    public void enQueue(T x) {
        if (x == null)
            return; // 空对象不能入队

        // 当队列满时，扩充容量
        if (this.front == (this.rear + 1) % this.element.length) {
            Object[] temp = this.element;
            // 重新申请一个容量更大的数组
            this.element = (T[]) new Object[temp.length * 2];
            int j = 0;
            // 按照队列元素次序复制数组元素
            for (int i = this.front; i != this.rear; i = (i + 1) % temp.length) {
                this.element[j++] = (T) temp[i];
            }
            this.front = 0;
            this.rear = j;
        }
        System.out.println("结点:[" + x + "],入队");
        this.element[this.rear] = x;
        this.rear = (this.rear + 1) % this.element.length;
    }

    /*
     * 出队，返回队头元素，若队列空返回null
     *
     * @see queue.QQueue#deQueue()
     */
    public T deQueue() {
        if (isEmpty()) // 若队列空返回null
            return null;
        T temp = (T) this.element[this.front]; // 取得队头元素
        this.element[front] = null;
        System.out.println("结点:[" + temp + "],出队");
        this.front = (this.front + 1) % this.element.length;
        return temp;
    }

    /**
     * 入队
     */
    public void enQueueByTag(T x) {
        if (x == null)
            return; // 空对象不能入队
        this.element[this.rear] = x;
        this.rear = (this.rear + 1) % this.element.length;
        if (rear == front) {
            tag = 1;
        }
    }

    public T deQueueByTag() {
        if (tag == 0) // 若队列空返回null
            return null;
        T temp = (T) this.element[this.front]; // 取得队头元素
        this.element[front] = null;
        this.front = (this.front + 1) % this.element.length;
        if (rear == front) {
            tag = 0;
        }
        return temp;
    }

    /*
     * 返回队列所有元素的描述字符串，形式为“(,)”，按照队列元素次序
     *
     * @see java.lang.Object#toString()
     */
    public String toString() {
        String str = "(";
        if (!isEmpty()) {
            str += this.element[this.front].toString();
            int i = (this.front + 1) % this.element.length;
            while (i != this.rear) {
                str += ", " + this.element[i].toString();
                i = (i + 1) % this.element.length;
            }
        } else {
            System.out.println("当前队列为空...");
            return "";
        }
//        System.out.println("当前队列(逻辑):" + str + "),队列长度=" + getNodeNum() + ",队头:" + getHead());
        this.printSeqQueue();
        return str + ")";
    }

    public String toStringByTag() {
        String str = "(";
        if (tag != 0) {
            str += this.element[this.front].toString();
            int i = (this.front + 1) % this.element.length;
            while (i != this.rear) {
                str += ", " + this.element[i].toString();
                i = (i + 1) % this.element.length;
            }
        } else {
            System.out.println("当前队列为空...");
            return "";
        }
//        System.out.println("当前队列(逻辑):" + str + "),队列长度=" + getNodeNumByTag() + ",队头:" + getHead());
        this.printSeqQueue();
        return str + ")";
    }

    /**
     * 获取队列中数据元素个数
     */
    private int getNodeNum() {
        int num = 0;
        if (!isEmpty()) {
            for (int i = 0; i < element.length; i++) {
                if (element[i] != null) {
                    num++;
                }
            }
        }
        return num;
    }

    /**
     * 获取队列中数据元素个数
     */
    private int getNodeNumByTag() {
        int num = 0;
        if (tag != 0) {
            for (int i = 0; i < element.length; i++) {
                if (element[i] != null) {
                    num++;
                }
            }
        }
        return num;
    }

    public void printSeqQueue() {
        String string = "[";
        if (front > rear) {
            for (int i = front; i < element.length; i++) {
                string += element[i] + ",";
            }
            for (int i = 0; i < rear; i++) {
                if (i != rear - 1) {
                    string += element[i] + ",";
                } else {
                    string += element[i] + "]";
                }
            }

        } else {
            for (int i = front; i < rear; i++) {
                if (i != rear - 1) {
                    string += element[i] + ",";
                } else {
                    string += element[i] + "]";
                }
            }
        }
        System.out.println("当前逻辑队列为:" + string);
        System.out.println("当前物理队列为:[");
        for (int i = 0; i < element.length; i++) {
            if (i != element.length - 1) {
                System.out.print(element[i] + ",");
            } else {
                System.out.print(element[i] + "]\n");
            }
        }
    }
}
